1. Field of the Invention
The present invention is related to computing sign text for branches of an electronic map network.
2. Description of the Related Art
Computers have revolutionized the idea of modeling a system for enhanced study and use of the system. One example is the modeling of a system as a network. A network is defined in its most general sense as something that includes a number of paths that interconnect or branch out. Many systems that involve decisions can be modeled as a network. For example, a manufacturing process or a system for providing medical treatment can be modeled as a network of decision points and actions between decision points. This network can be represented in electronic form and stored on a processor readable storage medium so that software can be created for using the network model to study or use the system.
An example of a useful network that can be stored in electronic form is an electronic map. The electronic map includes geographically referenced electronic data quantifying a physical, social, or economic system. The range of information included in an electronic map is virtually unlimited. For example, an electronic map of roads could include distances between elements, travel time, lot numbers, tax information, tourist information, processing time, waiting time, etc. Additionally, storing a map on a computer allows for a plethora of software applications to manipulate map data on the file.
Electronic maps, as well as other networks, can also be used for pathfinding, which is a method for computing a route between an origin and a destination. Some pathfinding systems compute a recommended route and guide the driver by highlighting the recommended route on a map display, or by giving turn-by-turn directions (via paper or display), or both. An electronic map that is used for pathfinding must carry information about the connectivity of a road network. In other words, the electronic map must contain information about the ways in which given road elements do or do not connect to each other (e.g., where there are ordinary intersections, where there are overpasses, where turns are restricted, etc.). A more detailed discussion regarding a system for pathfinding in an electronic map of roads can be found in U.S. Pat. No. 6,016,485, to Amakawa et al., incorporated herein by reference.
As costs for pathfinding systems continue to decrease, increasing numbers of drivers are purchasing car navigation systems for their commercial and personal vehicles. However, a pathfinding or car navigation system is useful only if the driving directions it offers are accurate. It is thus necessary to provide drivers not only with accurate path from the requested origin to the requested destination, but also accurate sign text for all guide signs (e.g., ramps, turns, etc.) along the path. To ensure the greatest possible accuracy, sign text for guide signs has traditionally been obtained by driving down the highway or freeway of interest and actually photographing the guide signs at each exit ramp. The sign text so obtained would then be incorporated into, for example, an electronic map of roads for use with a pathfinding or car navigation system.
The time and expense associated with this prior art approach in determining sign text are significant disadvantages. Moreover, there are instances where there are no signs to photograph as when the sign is missing. Accordingly, there is a need for a simple and inexpensive means for computing sign text for guide signs on exit ramps from limited access highways and freeways and for the branches from other carriageways.
The present invention, roughly described, provides a method of computing sign text for exits of a carriageway of a processor readable representation of a network. A first process is used to compute sign text for simple exit ramps of the carriageway and a second process is used to compute sign text for compound exit ramps of the carriageway. The first and second processes select route identifiers and/or street names from road elements in the network and carry them in a first and second name list. The first name list represents route identifiers and/or street names on a road element that crosses the carriageway ahead of the exit ramp for which sign text is to be computed by a distance parameter that is adjustable. The second name list represents route identifiers and/or street names on a road element that crosses the carriageway behind the exit ramp for which sign text is to be computed by another distance parameter that is also adjustable.
In accordance with the first process, if the simple exit ramp or simple ramp is identified by a route identifier, the route identifier is placed into a sign text variable without a directional. Otherwise, it must be determined whether a street name or a route identifier identifying a first road element connected to the end of the exit ramp matches a name or an entry in the first and second name lists. If there is a match, the matching street names or route identifiers are appended to the sign text variable. If there is no match, then it is further determined whether a second road element crossing the carriageway or highway ahead of or behind the exit ramp has a higher road class than that of the first road element. If the road class of the second road element is greater than that of the first road element then the name in the first name list is place into the sign text variable. Otherwise, the name list for the road element having the highest road class connected to the end of the exit ramp is placed in the sign text variable.
It must then be determined whether traffic exiting the simple exit ramp and continuing along the first road element proceeds in only one direction. If the sign text variable has a route identifier derived from a road element that connects to the end of the exit ramp, and if traffic exiting the ramp can proceed in only one direction along that road element, then a route directional is appended to the route identifier. If, however, the sign text variable has a street name derived from a road element that connects to the end of the exit ramp and if traffic exiting the exit ramp can proceed in only one direction along that road element, than a cardinal direction is appended to the street name. The compound sign text is subsequently outputted to a display.
In accordance with the second process for computing sign text for a compound exit ramp, the sign text for each leaf ramp of the compound exit ramp is computed using the first process. Then, working backwards from the leaf ramps, sign text for each fork of the compound exit ramp is computed. If both branches of the fork have the same names in their respective sign text variables, then the common value of the sign text variables for the branches of the fork is placed into the fork handle sign text variable. Otherwise, the sign text for both branches of the fork are combined into the fork handle sign text variable. Duplicate street names or route identifiers from the fork handle sign text variable are then removed and different versions of the same route identifier or the same name in the fork handle sign text is merged into a general version of the route identifier and the street name. The computed sign text is subsequently outputted to a display.
In one embodiment of the present invention, the sign text for respective exit ramps of the processor readable representation of a network is computed in real-time, in conjunction with a user initiated request to a system for finding a path between an origin and a destination in an electronic map of roads. In another embodiment of the present invention, the sign text for respective exit ramps of the processor readable representation of a network is computed and stored in a database.
The present invention can be accomplished using hardware, software, or a combination of both hardware and software. The software used for the present invention is stored on one or more processor readable storage media including hard disk drives, CD-ROMs, optical disks, floppy disks, RAM, ROM, or other suitable storage devices. In alternative embodiments, some or all of the software can be replaced by dedicated hardware including custom integrated circuits, gate arrays, FPGAs, PLDs, and special purpose computers.
These and other objects and advantages of the invention will appear more clearly from the following detailed description in which the preferred embodiment of the invention has been set forth in conjunction with the drawings.